/*
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.


How many such routes are there through a 20×20 grid?

Anser:137846528820
Time:16.006µs
*/
package main

import (
	"fmt"
	"time"
)

func main() {
	tstart := time.Now()
	grid := 20
	s := make([][]int, grid+1)
	for i := 0; i <= grid; i++ {
		s[i] = make([]int, grid+1)
		for j := 0; j <= grid; j++ {
			if i == 0 || j == 0 {
				s[i][j] = 1
			} else {
				s[i][j] = s[i-1][j] + s[i][j-1]
			}
		}
	}
	fmt.Println(s[grid][grid])
	tend := time.Now()
	fmt.Println(tend.Sub(tstart))
}
